import java.util.Arrays;

public class Solution498 {
    public int[] findDiagonalOrder(int[][] mat) {
        int m=mat.length,n=mat[0].length;
        int[] ans=new int[m*n];
        int x=0,y=0,count=1;
        ans[0]=mat[0][0];
        int[] dx={1,-1};
        int[] dy={-1,1};
        int d=0;
        while (count<m*n){
            if ((x==0 || x==m-1)&&(y!=n-1)){
                y++;
            }else{
                x++;
            }
            while (true){
                ans[count]=mat[x][y];
                count++;
                int xx=x+dx[d];
                int yy=y+dy[d];
                if (xx>=0 && xx<m && yy>=0 && yy<n){
                    x=xx;
                    y=yy;
                }else{
                    d=1-d;
                    break;
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new Solution498().findDiagonalOrder(new int[][]{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}})));
    }
}
